package sort;

import java.util.Arrays;

//堆排序
public class heap {
//    排序
    public static void a(int[] arr){
        b(arr);
        for (int i = arr.length; i >0; i--) {
            swap(arr,0,i-1);
            c(arr,0,i-1);
        }
        System.out.println(Arrays.toString(arr));
    }
//    初始化
    public static void b(int[]arr){
        for (int i = (arr.length-2)/2; i >=0; i--) {
            c(arr,i,arr.length);
        }
    }
//    向下调整
    public static void c(int[]arr,int parent,int len){
        int child=parent*2+1;
        while(child<len){
            if (child+1<len){
                if (arr[child]<=arr[child+1]&&arr[child+1]>arr[parent]){
                    child++;
                    swap(arr, parent, child);
                } else if (arr[child]>arr[child+1]&&arr[child]>arr[parent]) {
                    swap(arr, parent, child);
                }else {
                    return;
                }
            }else {
                if (arr[child]>arr[parent]){
                    swap(arr, parent, child);
                }else {
                    return;
                }
            }
            parent=child;
            child=parent*2+1;
        }
    }
    public static void swap(int[]arr,int a,int b){
        int temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
}
